package 二叉树;


/**
 * https://leetcode.cn/problems/diameter-of-binary-tree/?favorite=2cktkvj
 *
 * 题解：https://leetcode.cn/problems/diameter-of-binary-tree/solution/er-cha-shu-de-zhi-jing-by-leetcode-solution/
 *
 * 首先我们知道一条路径的长度为该路径经过的节点数减一，所以求直径（即求路径长度的最大值）等效于求路径经过节点数的最大值减一
 */
public class _543_二叉树的直径 {

    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        depth(root);
        return res - 1;
    }


    int res = 0;

    // depth函数的意思就是该root节点的最长深度，在这个过程中维护最长的直径
    private int depth(TreeNode root) {
        if (root == null) return 0;

        int left = depth(root.left);
        int right = depth(root.right);

        // 经过的节点数等于左子树+右子树深度+1
        res = Math.max(left + right + 1, res);

        // 节点的深度等于其左子树的深度，右子树的深度的最大值+1
        return Math.max(left, right) + 1;
    }
}
